Mudstock Bis

Limit pamięci: 32 MB

Władze zrzeszenia Holypolygons z okazji dziesiątej rocznicy pamiętnego pierwszego zlotu swoich członków na błoniach w Mudstock, postanowiły zorganizować wielki festiwal Mudstock bis.

Członkowie zrzeszenia mieszkają w wielu małych osadach Holypolylandii położonych wzdłuż linii kolejowych (gdzie ) ponumerowanych kolejnymi liczbami naturalnymi od do . Długość żadnej linii nie przekracza 500 km. Wszystkie linie mają początek w stolicy i biegną promieniście od stolicy ku obrzeżom kraju. Linie te nie krzyżują się. Każda osada nie będąca stolicą leży na dokładnie jednej linii. Na każdej linii liczba osad jest dodatnia i nie większa niż 100. Liczba członków zrzeszenia w jednej miejscowości również nie przekracza 100.

Każdą osadę, która nie jest stolicą identyfikujemy w jednoznaczny sposób za pomocą dwóch współrzędnych , gdzie to numer linii, na której leży osada, a to numer osady na linii. Osady na każdej z linii numerujemy kolejno od stolicy. Przyjmujemy, że stolica (która jest początkiem każdej linii) ma współrzędne .

Władze zrzeszenia fundują każdemu członkowi bilet kolejowy na powrót z festiwalu do miejsca zamieszkania. Cena biletu jest równa liczbie przejechanych kilometrów. Powstał więc problem, gdzie zorganizować festiwal, aby łączny koszt przejazdu koleją wszystkich członków zrzeszenia z festiwalu do domu był minimalny.

Zadanie

Ułóż program, który:

• wczytuje ze standardowego wejścia dane o sieci kolejowej: liczbę linii kolejowych, liczbę członków zrzeszenia mieszkających w stolicy oraz dla każdej osady liczbę mieszkających w niej członków stowarzyszenia i długość odcinka linii kolejowej od tej osady do najbliższej stacji w kierunku stolicy;
• znajduje miejscowość, w jakiej należy zorganizować festiwal, aby łączny koszt przejazdu koleją wszystkich jego uczestników (członków zrzeszenia) z festiwalu do domu był minimalny,
• oblicza ten minimalny łączny koszt przejazdów;
• zapisuje wyniki w standardowym wyjściu

Jeżeli dla wielu miejscowości łączny koszt przejazdu koleją wszystkich członków stowarzyszenia z danej miejscowości do domu jest minimalny, to Twój program powinien znajdować jedną z nich.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite: liczba linii kolejowych () oraz liczba członków zrzeszenia mieszkających w stolicy kraju ().

W kolejnych wierszach znajdują się opisy linii o kolejnych numerach od do . Każdy opis ma postać ciągu liczb całkowitych pooddzielanych pojedynczymi odstępami.

Najpierw jest podana dodatnia liczba miejscowości, które leżą na danej linii (nie licząc stolicy). Każda kolejna para liczb to: dodatnia odległość kolejnej osady na danej linii od najbliższej osady w kierunku stolicy oraz nieujemna liczba członków zrzeszenia mieszkających w tej osadzie. Bezpośrednio po ostatniej liczbie każdego opisu następuje koniec wiersza.

Dane w standardowym wejściu są zapisane poprawnie i Twój program nie musi tego sprawdzać.

Wyjście

W pierwszym wierszu standardowego wyjścia należy zapisać minimalny łączny koszt przejazdu koleją wszystkich członków stowarzyszenia z festiwalu do miejsca zamieszkania, a w drugim wierszu współrzędne osady, w której należy zorganizować festiwal.

Przykład

Dla danych wejściowych:

3 12
2 2 3 2 3
3 3 2 2 0 2 3
3 3 4 1 3 2 3

poprawną odpowiedzią jest:

87
0 0

Poniższy rysunek jest ilustracją testu przykładowego.

Autor zadania: Andrzej Walat.